
#include <vector>

using namespace std;

class Solution {
public:

    static bool comp(vector<int>& a, vector<int>& b) {
        if (a[0] == b[0]) {
            return a[1] > b[1];
        }
        return a[0] < b[0];
    }

    int maxEnvelopes(vector<vector<int>>& envelopes) {
        vector<int> result;

        sort(envelopes.begin(), envelopes.end(), comp);

        for (auto& e : envelopes) {
            auto it = lower_bound(result.begin(), result.end(), e[1]);
            if (it == result.end()) {
                result.push_back(e[1]);
            } else {
                *it = e[1];
            }
        }

        return result.size();
    }
};
